function shellSort(arr) {
  let len = arr.length;
  // gap 即为增量
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let j = i;
      let current = arr[i];
      while (j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
  return arr
}
const arr = [2, 1, 10, 8, 5, 4, 7.01, 3.3, 3, 9, 6, 0, -1, -2, 2 * 1, 3 * -1, 1 - 5, 2.13, 2.12]
console.log(shellSort(arr));

// * 希尔排序 --缩小增量排序  h有序  就是先让间隔h的位置有序
// 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。
// 它与插入排序的不同之处在于，它会优先比较距离较远的元素，减少了其复制的次数，速度要快很多。希尔排序又叫缩小增量排序。
// * 不稳定的排序算法 相等的元素可能会发生颠倒
// 希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。希尔排序能够解决一些初级排序算法无能为力的问题。